package GreedyAlgorithm;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 在一些项目中，规定了自己的启动资金，和这辈子可以干多少个项目，如何在最后挣最多的钱
 *
 * @author Liaorun
 */
public class IPO {

    public static class Node {
        public int p;
        public int c;

        public Node(int p, int c) {
            this.p = p;
            this.c = c;
        }
    }

    /**
     * 最小花费比较器
     */
    public static class MinCostComparator implements Comparator<Node> {

        @Override
        public int compare(Node o1, Node o2) {
            return o1.c - o2.c;
        }
    }

    /**
     * 最大收益比较器
     */
    public static class MaxProfitComparator implements Comparator<Node> {

        @Override
        public int compare(Node o1, Node o2) {
            return o1.c - o2.c;
        }
    }

    /**
     * 在一些项目中，知道项目的启动资金和纯利润
     * 规定了自己的启动资金，和这辈子可以干多少个项目，如何在最后挣最多的钱的算法
     *
     * @param k       一生可以干几个项目
     * @param w       启动资金
     * @param profits 项目的启动资金
     * @param capital 项目的纯利润
     * @return 最后自己有多少钱
     */
    public static int findMaximumCapital(int k, int w, int[] profits, int[] capital) {
        PriorityQueue<Node> minCostQ = new PriorityQueue<>(new MinCostComparator());
        PriorityQueue<Node> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());

        // 所有的项目按照启动资金从小到大排序
        for (int i = 0; i < profits.length; i++) {
            minCostQ.add(new Node(profits[i], capital[i]));
        }

        for (int i = 0; i < k; i++) {
            // 自己的资金可以干的项目按照收益从大到小排序
            while (!minCostQ.isEmpty() && minCostQ.peek().c <= w) {
                maxProfitQ.add(minCostQ.poll());
            }

            if (maxProfitQ.isEmpty()) {
                // 没有项目了，返回最终的钱数
                return w;
            }

            // 还有项目，找一个可以干的，利润最大的干
            w += maxProfitQ.poll().p;
        }

        return w;
    }
}
